'''
    一个分布式的探测多节点网络状态的python程序。
    每个节点，由一个server和一个client构成；每个节点运行相同的程序，节点间互相交换自己掌握的网络节点信息和各节点间的通信延迟数据。
    没有中心节点，每个节点都掌握整个网络（充分交换后）的连接状态。节点间每次只交换有限的数据（一个约400字节以内的UDP包），网络通信量不会随网络规模的扩大而增长。

    节点信息:
    {
        uuid:
        {
            n: hostname,
            i: [ip,ip,ip]
        }
    }

    client发给远端的包：
    {
        r: 随机数,
        v: major_version,
        i: remote ip,
        u: node uuid,
        n: node hostname,
        e: 交换的网络延迟信息,
        x: 交换的节点信息
    }

    远端返回给client的包：
    {
        r: client提供的随机数,
        i: client ip,
        u: node uuid,
        n: node hostname,
        e: 交换的网络延迟信息,
        x: 交换的节点信息
    }

    网络延迟信息:
    {
        ip>ip:
        {
            d: delay(us),
            s: timestamp
        }
    }
'''


from http.server import HTTPServer, BaseHTTPRequestHandler
import socketserver
import socket
import time
import random
import threading
import json
import uuid
import hashlib
import zlib
import urllib


#种子节点（用于帮其它节点接入网络）的IP
list_seed_node_ip = ["192.168.1.250"]
#list_seed_node_ip = ["127.0.0.1"]

#主版本，不同的主版本客户端不能通信
major_version = 2
#子版本
minor_version = 5

#当前节点的别名
node_host_name = socket.gethostname()
#代表当前节点身份的uuid
node_uuid = ''

#依据延迟时间进行节点分组的阈值上限
max_grouping_delay = 200 * 1000
#依据延迟时间进行节点分组的阈值下限
min_grouping_delay = 10 * 1000

#每轮连接的节点数
max_connect_nodes = 8
#每次交换的最大节点信息数
max_exchange_node_items = 3
#每次交换的最大网络延迟信息数
max_exchange_delay_items = 8

#每一轮的间隔（s）
interval_loop = 10
#一轮内不同目标的间隔（s）
interval_host_in_loop = 0.1
#socket超时（s）
timeout_socket = 3
#网络延迟信息的有效期（s）
timeout_delay_item = 60

#Server端口
server_port = 10001
#http端口
http_port = 6080

#所有已知节点信息
dict_nodes = {}
lock_dict_nodes = threading.Lock()
#可用交换节点IP列表
list_exchange_nodes_ip = list_seed_node_ip
lock_list_exchange_nodes_ip = threading.Lock()
#整个网络的延迟情况
dict_delay_between_nodes = {}
lock_dict_delay_between_nodes = threading.Lock()
#保护print
lock_print = threading.Lock()


'''
    client发给远端的包：
    {
        r: 随机数,
        v: major_version,
        i: remote ip,
        u: node uuid,
        n: node hostname,
        e: 交换的网络延迟信息,
        x: 交换的节点信息
    }
'''
def genClientPackage(remote_ip):
    pack = {
            'r': random.randint(1, 999999),
            'v': major_version,
            'i': remote_ip,
            'u': node_uuid,
            'n': node_host_name,
            'e': genExchangeDelayInfo(),
            'x': genExchangeNodeInfo()
            }
    return pack


def getRandomSampleDict(mydict, lock, max_num):
    exlist = {}
    lock.acquire()
    if len(mydict) > max_num:
        allkeys = list(mydict.keys())
        keys = random.sample(allkeys, max_num)
        exlist = {k:mydict[k] for k in keys}
    else:
        exlist = mydict
    lock.release()
    return exlist


def genExchangeDelayInfo():
    return getRandomSampleDict(dict_delay_between_nodes, lock_dict_delay_between_nodes, max_exchange_delay_items)


def genExchangeNodeInfo():
    return getRandomSampleDict(dict_nodes, lock_dict_nodes, max_exchange_node_items)


'''
    节点信息:
    {
        uuid:
        {
            n: hostname,
            i: [ip,ip,ip]
        }
    }
'''
def registerNode(uuid, hostname, ip):
    global dict_nodes
    lock_dict_nodes.acquire()
    if uuid in dict_nodes:
        if dict_nodes[uuid]['n'] != hostname:
            dict_nodes[uuid]['n'] = hostname
        if ip not in dict_nodes[uuid]['i']:
            dict_nodes[uuid]['i'].append(ip)
    else:
        dict_nodes[uuid] = {
            'n': hostname,
            'i': [ip]
        }
    lock_dict_nodes.release()


#从接收的网络延迟信息中提取出节点列表
def updateExchangeNodesIPList(dict_delay, reset=False):
    global list_exchange_nodes_ip
    lock_list_exchange_nodes_ip.acquire()
    if reset:
        list_exchange_nodes_ip = list(set(list_seed_node_ip).difference(set(dict_nodes[node_uuid]['i'])))
    for key in dict_delay:
        ips = key.split('>')
        for ip in ips:
            if (ip not in list_exchange_nodes_ip) and (ip not in dict_nodes[node_uuid]['i']):
                list_exchange_nodes_ip.append(ip)
    lock_list_exchange_nodes_ip.release()


'''
    当前节点到远端的延迟信息:
    {
        ip>ip:{
            d: delay(us),
            s: timestamp
        }
    }
'''
#记录当前节点到远端的延迟
def updateNetworkDelay(client_ip, remote_ip, delay):
    global dict_delay_between_nodes
    lock_dict_delay_between_nodes.acquire()
    if delay < 1:
        delay = 1
    else:
        delay = round(delay)
    dict_delay_between_nodes[client_ip + '>' + remote_ip] = {
        'd': delay,
        's': round(time.time())
    }
    lock_dict_delay_between_nodes.release()


#清理超时的记录
def cleanTimeoverDelayDict():
    global dict_delay_between_nodes
    lock_dict_delay_between_nodes.acquire()
    now = time.time()
    delKeys = []
    for key in dict_delay_between_nodes:
        ts = dict_delay_between_nodes[key]['s']
        if now - ts > timeout_delay_item:
            delKeys.append(key)
    for key in delKeys:
        del dict_delay_between_nodes[key]
    updateExchangeNodesIPList(dict_delay_between_nodes, True)
    lock_dict_delay_between_nodes.release()


#合并接收的网络延迟信息列表
def mergeDelayDict(new_dict_delay):
    global dict_delay_between_nodes
    lock_dict_delay_between_nodes.acquire()
    for item in new_dict_delay:
        if item in dict_delay_between_nodes:
            ts_remote = new_dict_delay[item]['s']
            ts_local = dict_delay_between_nodes[item]['s']
            if ts_remote > ts_local:
                dict_delay_between_nodes[item] = new_dict_delay[item]
        else:
            dict_delay_between_nodes[item] = new_dict_delay[item]
    lock_dict_delay_between_nodes.release()


#合并接收的节点信息列表
def mergeNodesDict(new_dict_nodes):
    global dict_nodes
    lock_dict_nodes.acquire()
    for item in new_dict_nodes:
        if item in dict_nodes:
            if dict_nodes[item]['n'] != new_dict_nodes[item]['n']:
                dict_nodes[item]['n'] = new_dict_nodes[item]['n']
            dict_nodes[item]['i'] = list(set(dict_nodes[item]['i']).union(set(new_dict_nodes[item]['i'])))
        else:
            dict_nodes[item] = new_dict_nodes[item]
    lock_dict_nodes.release()


def isLocalIP(ip):
    res = False
    lock_dict_nodes.acquire()
    res = (ip in dict_nodes[node_uuid]['i'])
    lock_dict_nodes.release()
    return res


class myDelayTestThread(threading.Thread):
    remote_ip = ''

    def __init__(self, thread_name, remote_ip):
        super(myDelayTestThread, self).__init__(name = thread_name)
        self.remote_ip = remote_ip
        
    def run(self):
        sendPack = genClientPackage(self.remote_ip)
        sendData = json.dumps(sendPack, ensure_ascii=False, sort_keys=False).encode()
        sendData_z = zlib.compress(sendData)

        recvData_z = b''
        t1 = time.perf_counter()
        try:
            socket.setdefaulttimeout(timeout_socket)
            client = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
            client.sendto(sendData_z, (self.remote_ip, server_port))
            recvData_z, recv_addr = client.recvfrom(4096)
            client.close()
        except Exception as err:
            tnow = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
            lock_print.acquire()
            print("[%s] to: %s delay: loss" % (tnow, self.remote_ip))
            lock_print.release()
            return
        t2 = time.perf_counter()

        recvPack = {}
        try:
            recvData = zlib.decompress(recvData_z).decode()
            recvPack = json.loads(recvData)
            if recvPack['r'] != sendPack['r']:
                raise Exception('bad respond')
        except Exception as err:
            tnow = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
            lock_print.acquire()
            print("[%s] to: %s delay: bad" % (tnow, self.remote_ip))
            lock_print.release()
            return

        #注册对方节点信息
        registerNode(recvPack['u'], recvPack['n'], self.remote_ip)
        #根据对方提供的信息，注册本节点的ip
        registerNode(node_uuid, node_host_name, recvPack['i'])
        if recvPack['u'] != node_uuid:
            #更新可用交换节点IP地址列表
            updateExchangeNodesIPList(recvPack['e'])
            #记录对方提供的网络延迟信息
            mergeDelayDict(recvPack['e'])
            #记录对方提供的节点信息
            mergeNodesDict(recvPack['x'])
            #计算两个节点间的延迟(us)
            tdelt = (t2-t1)*1000*1000/2
            #记录本次测量的网络延迟信息
            updateNetworkDelay(recvPack['i'], self.remote_ip, tdelt)
            
            tnow = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
            lock_print.acquire()
            print("[%s] to: %s delay: %dus" % (tnow, self.remote_ip, round(tdelt)))
            #print(sendPack)
            #print(recvPack)
            #print()
            lock_print.release()


class myClientThread(threading.Thread):

    def __init__(self, thread_name):
        super(myClientThread, self).__init__(name = thread_name)

    def run(self):
        time.sleep(2)
        print("Client Running on Interval: %ds" % interval_loop)
        print("max_connect_nodes = %d" % max_connect_nodes)
        print("max_exchange_delay_items = %d" % max_exchange_delay_items)
        print("max_exchange_node_items = %d" % max_exchange_node_items)
        print()

        loopCount = 0
        while True:
            remote_ips = []
            if len(list_exchange_nodes_ip) > max_connect_nodes:
                remote_ips = random.sample(list_exchange_nodes_ip, max_connect_nodes)
            else:
                remote_ips = list_exchange_nodes_ip

            tnow = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
            threadList = []
            for ip in remote_ips:
                threadList.append(myDelayTestThread(tnow + ' ' + ip, ip))
            for thread in threadList:
                thread.start()
                time.sleep(interval_host_in_loop)
            for thread in threadList:
                thread.join()

            cleanTimeoverDelayDict()
            #每10分钟保存一次状态数据
            if loopCount % (600 / interval_loop) == 0:
                dumpStatus()
            loopCount += 1
            
            '''
            lock_print.acquire()
            print()
            print('----------------------')
            lock_list_exchange_nodes_ip.acquire()
            print('exchange node ip:')
            print(list_exchange_nodes_ip)
            lock_list_exchange_nodes_ip.release()
            lock_dict_nodes.acquire()
            print('node list:')
            print(dict_nodes)
            lock_dict_nodes.release()
            lock_dict_delay_between_nodes.acquire()
            print('network delay list:')
            print(dict_delay_between_nodes)
            lock_dict_delay_between_nodes.release()
            print('----------------------')
            print()
            lock_print.release()
            '''
            time.sleep(interval_loop)


'''
    远端返回给client的包：
    {
        r: client提供的随机数,
        i: client ip,
        u: node uuid,
        n: node hostname,
        e: 交换的网络延迟信息,
        x: 交换的节点信息
    }
'''
class MyUDPHandler(socketserver.BaseRequestHandler):
    def handle(self):
        recvData_z, server = self.request
        sendPack = {}
        recvPack = {}
        try:
            recvData = zlib.decompress(recvData_z).decode()
            recvPack = json.loads(recvData)
            if recvPack['v'] != major_version:
                return
            sendPack['r'] = recvPack['r']
            sendPack['i'] = self.client_address[0]
            sendPack['u'] = node_uuid
            sendPack['n'] = node_host_name
            sendPack['e'] = genExchangeDelayInfo()
            sendPack['x'] = genExchangeNodeInfo()
            sendData = json.dumps(sendPack, ensure_ascii=False, sort_keys=False).encode()
            sendData_z = zlib.compress(sendData)
            server.sendto(sendData_z, self.client_address)

            #注册对方节点信息
            registerNode(recvPack['u'], recvPack['n'], self.client_address[0])
            #根据对方提供的信息，注册本节点的ip
            registerNode(node_uuid, node_host_name, recvPack['i'])
            #更新可用交换节点IP地址列表
            updateExchangeNodesIPList(recvPack['e'])
            #记录对方提供的网络延迟信息
            mergeDelayDict(recvPack['e'])
            #记录对方提供的节点信息
            mergeNodesDict(recvPack['x'])
        except Exception as err:
            lock_print.acquire()
            print('Server Exception:')
            print(err)
            lock_print.release()


def dumpStatus():
    lock_dict_nodes.acquire()
    lock_dict_delay_between_nodes.acquire()
    status = {
        'major_version': major_version,
        'minor_version': minor_version,
        'uuid': node_uuid,
        'nodes': dict_nodes,
        'delay': dict_delay_between_nodes
    }
    lock_dict_delay_between_nodes.release()
    lock_dict_nodes.release()
    try:
        with open('ndt_node_status.json', 'w') as json_file:
            json.dump(status, json_file, ensure_ascii=False, sort_keys=False)
    except Exception as err:
        lock_print.acquire()
        print(err)
        lock_print.release()

        
def loadStatus():
    global node_uuid, dict_nodes, dict_delay_between_nodes
    try:
        with open('ndt_node_status.json', 'r') as json_file:
            status = json.load(json_file)
            if status['major_version'] == major_version:
                node_uuid = status['uuid']
                dict_nodes = status['nodes']
                dict_delay_between_nodes = status['delay']
                updateExchangeNodesIPList(dict_delay_between_nodes, True)
                return True
            else:
                return False
    except Exception as err:
        lock_print.acquire()
        print(err)
        lock_print.release()
        return False


def genNodeListTable():
    table = [['&emsp;&emsp;UUID&emsp;&emsp;', '&emsp;&emsp;&emsp;Host Name&emsp;&emsp;&emsp;', '&emsp;&emsp;IP Address&emsp;&emsp;']]
    lock_dict_nodes.acquire()
    for uuid in dict_nodes:
        line = [uuid, dict_nodes[uuid]['n']]
        ips = dict_nodes[uuid]['i']
        ips.sort()
        if len(ips) == 0:
            line.append(' ')
        else:
            line.append(ips[0])
            table.append(line)
            if len(ips) > 1:
                for ip in ips[1:]:
                    table.append([' ', ' ', ip])
    lock_dict_nodes.release()

    htmlTable = '<table border="1" style="text-align:center">'
    for row in table:
        htmlTable += '<tr>'
        for col in row:
            htmlTable += '<td>'
            htmlTable += col
            htmlTable += '</td>'
        htmlTable += '</tr>'
    htmlTable += '</table>'
    return htmlTable


def genNetworkDelayTable():
    set_ip = set()
    table = []
    now = time.time()
    lock_dict_delay_between_nodes.acquire()

    for ipPair in dict_delay_between_nodes:
        ips = ipPair.split('>')
        set_ip.add(ips[0])
        set_ip.add(ips[1])
        
    list_ip = list(set_ip)
    list_ip.sort()
    table.append([' '] + list_ip)
    for ip_row in list_ip:
        line = [ip_row]
        for ip_col in list_ip:
            if ip_row+'>'+ip_col in dict_delay_between_nodes:
                if now - dict_delay_between_nodes[ip_row+'>'+ip_col]['s'] > timeout_delay_item:
                    line.append('timeout')
                else:
                    line.append(format(dict_delay_between_nodes[ip_row+'>'+ip_col]['d'], ','))
            else:
                line.append(' ')
        table.append(line)

    lock_dict_delay_between_nodes.release()

    htmlTable = '<table border="1" style="text-align:center">'
    for row in table:
        htmlTable += '<tr>'
        for col in row:
            htmlTable += '<td>'
            htmlTable += col
            htmlTable += '</td>'
        htmlTable += '</tr>'
    htmlTable += '</table>'
    return htmlTable


def genNodeGroupTable():
    groups = groupNodes()
    i = 0
    htmlTable = '<table border="1" style="text-align:center">'
    for row in groups:
        row.sort()
        i += 1
        htmlTable += '<tr>'
        htmlTable += '<td>&emsp;Group&ensp;%d&emsp;</td>' % i
        for ip in row:
            htmlTable += '<td>&ensp;'
            htmlTable += ip
            htmlTable += '&ensp;</td>'
        htmlTable += '</tr>'
    htmlTable += '</table>'
    return htmlTable


#查找样本值的分界点
def findSamplesMiddle():
    samples = []
    now = time.time()

    lock_dict_delay_between_nodes.acquire()
    for ipPair in dict_delay_between_nodes:
        if now - dict_delay_between_nodes[ipPair]['s'] <= timeout_delay_item:
            samples.append(dict_delay_between_nodes[ipPair]['d'])
    lock_dict_delay_between_nodes.release()

    samples.sort()
    diffList = []
    for i in range(len(samples) - 1):
        diffList.append(samples[i+1] - samples[i])
    max_diff = diffList.index(max(diffList))
    return round((samples[max_diff + 1] - samples[max_diff]) / 2)


def groupNodes():
    midVal = findSamplesMiddle()
    if midVal > max_grouping_delay:
        midVal = max_grouping_delay
    elif midVal < min_grouping_delay:
        midVal = min_grouping_delay

    groups = []
    now = time.time()

    lock_dict_delay_between_nodes.acquire()
    
    set_ip = set()
    for ipPair in dict_delay_between_nodes:
        ips = ipPair.split('>')
        set_ip.add(ips[0])
        set_ip.add(ips[1])

    while(len(set_ip) > 0):
        group = set()
        ip = set_ip.pop()
        group.add(ip)
        for ipPair in dict_delay_between_nodes:
            if ipPair.find(ip) >= 0:
                if now - dict_delay_between_nodes[ipPair]['s'] <= timeout_delay_item:
                    d = dict_delay_between_nodes[ipPair]['d']
                    if d < midVal:
                        ips = ipPair.split('>')
                        group.add(ips[0])
                        group.add(ips[1])
                        set_ip.discard(ips[0])
                        set_ip.discard(ips[1])
        groups.append(list(group))
    
    lock_dict_delay_between_nodes.release()
    return groups


class myHttpHandler(BaseHTTPRequestHandler):
    def do_GET(self):
        querypath = urllib.parse.urlparse(self.path).path
        if querypath == r'/status':
            timenow = time.strftime('%Y-%m-%d %H:%M:%S', time.localtime())
            table1 = genNodeListTable()
            table2 = genNodeGroupTable()
            table3 = genNetworkDelayTable()
            sendData = timenow + '<br><br>' + table1 + '<br><br>' + table2 + '<br><br>' + table3
            try:
                self.send_response(200)
                self.send_header('Content-Type', 'text/html')
                self.send_header('Content-Length', str(len(sendData)))
                self.end_headers()
                self.wfile.write(sendData.encode())
            except Exception as err:
                print(err)


class myHttpServerThread(threading.Thread):

    def __init__(self, thread_name):
        super(myHttpServerThread, self).__init__(name = thread_name)

    def run(self):
        http_server = HTTPServer(('0.0.0.0', http_port), myHttpHandler)
        print("NDT Http Server Running on Port %d ......" % http_port)
        print()
        print("http://127.0.0.1:%d/status" % http_port)
        print()
        http_server.serve_forever()


if __name__ == "__main__":
    print()
    print("Network Delay Test Node V%d.%d" % (major_version, minor_version))
    print()

    if loadStatus():
        print("Load Status Success")
    else:
        node_uuid = hashlib.md5(uuid.uuid1().bytes).hexdigest()[:12]
        dict_nodes = {node_uuid:{'n':node_host_name, 'i':[]}}
        dumpStatus()
    print("NDT Node Host Name: " + node_host_name)
    print("NDT Node UUID: " + node_uuid)
    print()
    
    myClientThread("NDT_Client_Thread").start()
    myHttpServerThread("NDT_Http_Server_Thread").start()

    server = socketserver.ThreadingUDPServer(("0.0.0.0", server_port), MyUDPHandler)
    print("NDT Server Running on UDP Port %d ......" % (server_port))
    print()
    server.serve_forever()